// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;

import java.util.Stack;



class ReverseFiniteAutomataBuilder implements StateVisitor {
  FiniteAutomata build(final FiniteAutomata fa) {
    final FiniteAutomata result = reverse(fa);
    result.append(new MatchState());
    assert result.size() == fa.size();
    return result;
  }

  public void visit(final MatchState s) {
    // Алгоритм предполагает, что любой конечный автомат содержит единственный
    // MatchState последним состоянием.
    assert s == fa_.get(fa_.size() - 1);
  }

  public void visit(final JumpState s) {
    assert false;  // должны удаляться при обработке ForkState
  }

  public void visit(final ForkState s) {
    // Допустим, что автомат имеет вид 0 -> FA -> 1,
    // где FA, один из рассмотренных ниже вариантов.
    // Алгоритм работает на допущении,
    // что возможно только 3 случая использования ForkState:
    //                        /---------------v
    //  - (xy)?        0 -> Fork -> x -> y -> 1
    //
    //                        v----------------\
    //  - (xy)*        0 -> Fork -> x -> y -> Jump  1
    //                        \---------------------^
    //
    //                        /---------------------v
    //  - (xy|ab)      0 -> Fork -> x -> y -> Jump  a -> b -> 1
    //                                          \-------------^
    //
    // Таким образом:
    //   - Fork стоит всегда левее остальных состояний и не нужно исправлять
    //     состояния в deque_ (поэтому для (xy)+ используется xy(xy)*)
    //   - Ветки идут последовательно и длина одной из них вычисляется как
    //     (начало правой - Fork).
    //   - Ветки или пересекутся в состоянии 1 или Jump переходит в Fork (назад)
    //
    // Алгоритм вычисляет ветки и рекурсивно применяется к ним.

    final int left = Math.min(s.next(), s.next_low());
    final int right = Math.max(s.next(), s.next_low());
    final boolean lazy = s.next() == right;  // если это случаи 1 или 2.
    assert left == 1 && right > left;

    final FiniteAutomata fa_left = new FiniteAutomata();
    for ( int i = left ; i != right - 1 ; i++ ) {  // не включая возможный Jump
      fa_left.append(state(current_state_id_ + i));
    }


    final int case_;
    final FiniteAutomata fa_right = new FiniteAutomata();
    final State last_state_of_left = state(current_state_id_ + right - 1);

    if ( last_state_of_left instanceof JumpState ) {
      final int next = ((JumpState)last_state_of_left).next();
      if ( next > 0 ) {
        assert next > 1;
        case_ = '|';
        for ( int i = right ; i != right - 1 + next ; i++ ) {
          fa_right.append(state(current_state_id_ + i));
        }
      } else {
        assert next == - ( fa_left.size() + 1 );
        case_ = '*';
      }
    } else {
      case_ = '?';
      fa_left.append(last_state_of_left); // возвращаем не Jump состояние
    }


    final ReverseFiniteAutomataBuilder v = new ReverseFiniteAutomataBuilder();
    final FiniteAutomata r_fa_left = v.reverse(fa_left);
    final FiniteAutomata r_fa_right = v.reverse(fa_right);

    switch ( case_ ) {
      case '?': r_fa_left.zeroOrOne(lazy); break;
      case '*': r_fa_left.zeroOrMore(lazy); break;
      case '|': r_fa_left.alternative(r_fa_right); break;
      default: assert false;
    }

    // Кладем в стек в обратном порядке, чтобы при построении результата
    // он восстановился (фактически это очередь через 2 стека).
    for ( int i = r_fa_left.size() - 1 ; i != -1 ; i-- ) {
      stack_.push(r_fa_left.get(i));
    }

    // JumpState добавится только в случаях '*' и '|', но в fa_left его нет.
    assert r_fa_left.size() == 1 + fa_left.size() + fa_right.size() +
                               ( case_ == '?' ? 0 : 1 );
    // -1, так как в reverse после выполнения данного метода будет +1.
    current_state_id_ += r_fa_left.size() - 1;
  }

  public void visit(final BeginSaveState s) {
    stack_.push(new EndSaveState(s.submatch_num()));
  }

  public void visit(final EndSaveState s) {
    stack_.push(new BeginSaveState(s.submatch_num()));
  }

  // ^ -> \\z
  public void visit(final BeginningAnchorState s) {
    stack_.push(new EndOfStringAnchorState());
  }

  // \\z -> \\A
  public void visit(final EndOfStringAnchorState s) {
    stack_.push(new BeginningAnchorState());
  }

  // $ -> Rev$
  public void visit(final EndingAnchorState s) {
    stack_.push(new ReverseEndingAnchorState());
  }

  public void visit(final ReverseEndingAnchorState s) {
    assert false;
  }

  // \\A -> \\z
  public void visit(final StringBeginningAnchorState s) {
    stack_.push(new EndOfStringAnchorState());
  }

  // \\Z -> Rev$
  public void visit(final StringEndingAnchorState s) {
    stack_.push(new ReverseEndingAnchorState());
  }

  // ^ML -> $ML
  public void visit(final MultiLineBeginningAnchorState s) {
    stack_.push(new MultiLineEndingAnchorState());
  }

  // $ML -> ^ML
  public void visit(final MultiLineEndingAnchorState s) {
    stack_.push(new MultiLineBeginningAnchorState());
  }

  public void visit(final WordBoundaryAnchorState s) { stack_.push(s); }
  public void visit(final InvertedWordBoundaryAnchorState s) { stack_.push(s); }
  public void visit(final DotState s) { stack_.push(s); }
  public void visit(final DotAllState s) { stack_.push(s); }
  public void visit(final CharacterState s) { stack_.push(s); }
  public void visit(final CaseCharacterState s) { stack_.push(s); }
  public void visit(final CharacterGroupState s) { stack_.push(s); }
  public void visit(final CaseCharacterGroupState s) { stack_.push(s); }


  private State state(final int state_id) {
    return fa_.get(state_id);
  }

  private FiniteAutomata reverse(final FiniteAutomata fa) {
    fa_ = fa;
    stack_.clear();

    current_state_id_ = 0;
    while ( current_state_id_ < fa_.size() ) {
      // может измениться current_state_id_
      state(current_state_id_).accept(this);
      current_state_id_++;
    }

    final FiniteAutomata result = new FiniteAutomata();
    while ( !stack_.isEmpty() ) {
      result.append(stack_.pop());
    }
    return result;
  }

  private FiniteAutomata fa_;
  private final Stack<State> stack_ = new Stack<State>();
  private int current_state_id_;
}
